package LinkedList;

public class MySingleList implements IList {

    public MySingleList() {
        createList();
    }

/*
* 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]
*
* 两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
*
* https://leetcode.cn/problems/merge-two-sorted-lists/description/
 */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        ListNode NewListNode=new ListNode(-1);
        ListNode cur=NewListNode;


        while(list1!=null && list2!=null){
            if(list1.val<list2.val){
                cur.next=list1;
                list1=list1.next;
                cur=cur.next;

            }else{
                cur.next= list2;
                list2= list2.next;
                cur=cur.next;

            }

        }

        if(list1==null){
            cur.next=list2;

        }else
            cur.next=list1;
        return NewListNode.next;
    }
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    //链表的属性  链表的头节点
    public ListNode head;//null



    public ListNode reverseList() {

        if(head.next==null){
            return head;
        }
        if(head==null){
            return head;
        }
        ListNode cur=head.next;//待反转的节点
        head.next=null;
        while(cur!=null){//翻转链表
            ListNode Nextcur=cur.next;//待反转的下一个节点
            cur.next=head;
            head=cur;
            cur=Nextcur;
        }
        return head;

    }

    public void createList() {
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        this.head = node1;
    }

    /*
    * 头插法
    * */
    @Override
    public void addFirst(int data) {

        ListNode listNode=new ListNode(data);
        listNode.next=this.head;
        this.head=listNode;


    }

    /*
    * 尾插法
    * */
    @Override
    public void addLast(int data) {

        ListNode node=new ListNode(data);
        ListNode cur=head;
        if(head==null){
            node=this.head;
            return;
        }
        while (cur.next!=null){

            cur=cur.next;
        }
        cur.next=node;
    }

    /*
    * 指定插入
    * */
    @Override
    public void addIndex(int index, int data) {

        ListNode  NewNode=new ListNode(data);//新的节点
        ListNode cur=this.head;

        if(index<0 && index>size()){

            throw new indexException("index下标不合法"+index);

        }
        if(head==null){
            head=NewNode;
            return;
        }
        if(head.next==null){
            NewNode.next=head;
            head=NewNode;
            return;
        }
        if(size()==index){
            addLast(data);
            return;
        }

        ListNode prevNode=NodeIndex(index);//插入节点的前一个节点
        NewNode.next=prevNode.next;
        prevNode.next=NewNode;
    }

    private ListNode NodeIndex(int index){
        int count=0;
        ListNode cur=this.head;
        while (count!=index-1){
            cur=cur.next;
        }
        return cur;
    }
    /*
    * 查找当前链表有没有key值！
    * */
    @Override
    public boolean contains(int key) {
        ListNode listNode=head;


        while (listNode!=null){

            if(listNode.val==key){
                return true;
            }
            listNode=listNode.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(head.val==key){//第一个就是就找到要删除的元素
            head=head.next;
            return;
        }
        if(head==null){//链表为空
            return;
        }


     ListNode listNode=findPrevKey(key); //查找前区
     if(listNode!=null){
         return;//没有你要删除的数字
     }
     ListNode del=listNode.next.next;
     listNode.next=del;


    }

    private ListNode findPrevKey(int key){

        ListNode listNode=head;
        while ( listNode.next!=null){

            if(listNode.next.val==key){

                return listNode;
            }else
                listNode=listNode.next;

        }
        return null;
    }
    @Override
    public void removeAllKey(int key) {
        ListNode prev=this.head;//表示可能要删除节点的前驱
        ListNode cur=this.head.next;//可能要删除的节点

        while(cur!=null){//删除所有是key的节点(没有判断头节点的值)
            if(cur.val!=key){
                cur=cur.next;
                prev=prev.next;

            }else{
                cur=cur.next;
                prev.next=cur;
            }

        }

        if(head.val==key){
            head=head.next;
        }


    }

    /*
    *
    * 有多少的节点*/
    @Override
    public int size() {
        ListNode listNode=head;
        int count=0;
        while (listNode!=null){

            count++;
           listNode= listNode.next;
        }

        return count;
    }

    @Override
    public void clear() {
        this.head=null;
        return;
    }
//
//
//打印节点
/*
// */

public void display(ListNode l) {
    ListNode listNode=head;

    while((listNode)!=null){

        System.out.print(listNode.val);
        listNode=listNode.next;

        System.out.print(" ");
    }
    System.out.println("");

}

    @Override
    public void display() {
        ListNode listNode=head;

        while((listNode)!=null){

            System.out.print(listNode.val);
            listNode=listNode.next;

            System.out.print(" ");
        }
        System.out.println("");

    }
    /*
    * 查找中间节点
    *
    * */

    public ListNode middleNode(){

        ListNode fast=head;
        ListNode slow=head;
        ListNode cur=head;

        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;

        /*int count=0;
        while (cur!=null){

            count++;
            cur=cur.next;
        }
        if(count%2==0){
            while (fast!=null){
                fast=fast.next.next;
                slow=slow.next;
            }
            return slow;
        }else {
            while (fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
            }
            return slow;
        }
*/



    }

}
